A Novel Approach to Finding Near-Cliques: The Triangle-Densest Subgraph Problem

摘要

Many graph mining applications rely on detecting subgraphs which arenear-cliques. There exists a dichotomy between the results in the existing workrelated to this problem: on the one hand the densest subgraph problem (DSP)which maximizes the average degree over all subgraphs is solvable in polynomialtime but for many networks fails to find subgraphs which are near-cliques. Onthe other hand, formulations that are geared towards finding near-cliques areNP-hard and frequently inapproximable due to connections with the MaximumClique problem. In this work, we propose a formulation which combines the best of bothworlds: it is solvable in polynomial time and finds near-cliques when the DSPfails. Surprisingly, our formulation is a simple variation of the DSP.Specifically, we define the triangle densest subgraph problem (TDSP): given$G(V,E)$, find a subset of vertices $S^*$ such that $\tau(S^*)=\max_{S\subseteq V} \frac{t(S)}{|S|}$, where $t(S)$ is the number of triangles inducedby the set $S$. We provide various exact and approximation algorithms which thesolve the TDSP efficiently. Furthermore, we show how our algorithms adapt tothe more general problem of maximizing the $k$-clique average density. Finally,we provide empirical evidence that the TDSP should be used whenever the outputof the DSP fails to output a near-clique.